/**
 * @author heguochang
 * @version Id: Exercise2.java, v 0.1 2021/10/17 下午11:57 heguochang Exp $$
 * <p>
 * 统计n以内的素数个数
 * 素数:只能被1和自身整除的自然数,0,1除外
 * <p>
 * 例如:输入100
 * 输出25
 * <p>
 * 重点考察:埃筛法
 */
public class Exercise3 {

    public static void main(String[] args) {
        System.out.println(bf(100));
    }

    // 暴力算法
    public static int bf(int n) {
        // 定义一个计算器,统计素数
        int count = 0;

        for (int i = 2; i < n; i++) {
            count += isPrime(i) ? 1 : 0;
        }

        return count;
    }

    // 判断
    private static boolean isPrime(int x) {
        // 从2开始尝试进行整除,能被整除说明不是一个素数
        for (int i = 2; i < x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * eg:暴力判断12时,有
     * 2*6,3*4
     * 4*3,6*2
     * 实际上只需要判断前半段就可以,实际都是 根号12 * 根号12
     * 所以临界值到小于 根号12就可以
     * 如果这个数不是素数,就会从头找到尾,造成浪费,所以写成i*i<x,等同于i<根号x
     *
     * @param x
     * @return
     */
    private static boolean isPrime2(int x) {
        // 从2开始尝试进行整除,能被整除说明不是一个素数
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}